package net.ericaro.neogrex;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;

/**
 * Class defining:
 * <ul>
 * <li>underlying directed graph</li>
 * <li>the input vertex</li>
 * <li>the outputs vertices</li>
 * </ul>
 * 
 * @author eric
 * 
 * @param <S>
 *            any state class
 * @param <T>
 *            any transition class
 */
public abstract class Grex<S, T> {

	protected DirectedSparseMultigraph<S, T> g = new DirectedSparseMultigraph<S, T>();
	protected S in;
	protected Set<S> outs = new HashSet<S>();

	public Grex() {
		super();
	}

	/**
	 * Construct a simple Grex with a single transition, and two states.
	 * 
	 * @param t
	 * @param src
	 * @param target
	 */
	public Grex(T t, S src, S target) {
		this();
		g.addEdge(t, src, target);
		this.in = src;
		this.outs.add(target);
		assertGraph();
	}

	/**
	 * returns a new Grex result of ( this , that )
	 * 
	 * @param that
	 * @return
	 */
	public <G extends Grex<S, T>> G seq(G that) {

		G n = newInstance();

		// graph operations
		Map<S, S> mapThis = this.copyGraphInto(n);
		Map<S, S> mapThat = that.copyGraphInto(n);

		boolean io = (that.outs.contains(that.in));
		for (S out : this.outs) {
			n.mergeOutbounds(mapThat.get(that.in), mapThis.get(out));
			if (io)
				n.outs.add(mapThis.get(out));
		}

		//bounds
		n.in = mapThis.get(this.in);
		for (S out : that.outs)
			n.outs.add(mapThat.get(out));

		n.g.removeVertex(mapThat.get(that.in));
		n.outs.remove(mapThat.get(that.in));
		n.assertGraph();
		return n;
	}

	/** returns a new Grex result of  ( this |  that )
	 * 
	 * @param that
	 * @return
	 */
	public <G extends Grex<S, T>> G sel(G that) {

		G n = newInstance();

		// graph operations
		Map<S, S> mapThis = this.copyGraphInto(n);
		Map<S, S> mapThat = that.copyGraphInto(n);

		//bounds
		n.in = n.merge(mapThis, this.in, mapThat, that.in);

		for (S out : that.outs)
			n.outs.add(mapThat.get(out));
		for (S out : this.outs)
			n.outs.add(mapThis.get(out));

		n.assertGraph();
		return n;
	}

	/** returns a new Grex result of  ( this )+
	 * 
	 * @param that
	 * @return
	 */
	public <G extends Grex<S, T>> G plus() {

		// graph
		G n = dup();
		//bounds
		for (S out : n.outs)
			n.mergeOutbounds(n.in, out);

		n.assertGraph();
		return n;

	}

	/** returns a new Grex result of  ( this )?
	 * 
	 * @param that
	 * @return
	 */
	public <G extends Grex<S, T>> G opt() {
		G n = dup();
		n.outs.add(n.in);
		n.assertGraph();
		return n;

	}

	/** returns a new Grex result of  ( this )*
	 * 
	 * @param that
	 * @return
	 */
	public <G extends Grex<S, T>> G star() {
		return plus().opt();
	}

	// INTERNAL STUFF
	
	/** assert that the grex is valid (no null, and every context vertices belongs to the graph
	 * 
	 */
	<G> void assertGraph() {
		assert in != null : "impossible null in state";
		assert outs != null && outs.size() != 0 : "impossible null outs set";
		assert g != null : "impossible null graph";
		for (S out : outs) {
			assert out != null : "impossible null out state";
			assert g.containsVertex(out) : "out node is not in the graph";
		}
		assert g.containsVertex(in) : "in does not belong to this graph";
	}

	/** simply clone this all transition and vertices in the target graph
	 * 
	 * @param target
	 * @return
	 */
	<G extends Grex<S, T>> Map<S, S> copyGraphInto(G target) {
		Map<S, S> map = new HashMap<S, S>();
		for (S s : this.g.getVertices()) {
			S c = target.newState(); // clone
			map.put(s, c); // keep for transition clone
			target.g.addVertex(c); // append to the new graph
		}
		for (T t : this.g.getEdges())
			target.g.addEdge(target.cloneTransition(t), map.get(this.g.getSource(t)), map.get(this.g.getDest(t)));
		return map;
	}
	
	/** merge two vertex:
	 * creates a new vertex, and copy all inputs, and all outputs from s1 and from s2.
	 * if a map m_i is given it assume that s_i belongs to another graph, and that the actual one should
	 * be looked into the map.
	 * the map is updated with creation of the merged element, and deletion of the previous items.
	 * 
	 * @param m1
	 * @param s1
	 * @param m2
	 * @param s2
	 * @return
	 */
	S merge(Map<S, S> m1, S s1, Map<S, S> m2, S s2) {

		S ms1 = (m1 == null ? s1 : m1.get(s1));
		S ms2 = (m2 == null ? s2 : m2.get(s2));

		S m = mergeRaw(ms1, ms2);
		if (m1 != null)
			m1.put(s1, m);
		if (m2 != null)
			m2.put(s2, m);
		return m;
	}

	S mergeRaw(S s1, S s2) {
		S s = newState();
		Set<T> incomings = new HashSet<T>();
		incomings.addAll(g.getInEdges(s1));
		incomings.addAll(g.getInEdges(s2));
		for (T t : incomings) {
			S src = g.getSource(t);
			g.removeEdge(t);
			g.addEdge(t, src, s);
		}
		Set<T> outgoings = new HashSet<T>();
		outgoings.addAll(g.getOutEdges(s1));
		outgoings.addAll(g.getOutEdges(s2));
		for (T t : outgoings) {
			S dest = g.getDest(t);
			g.removeEdge(t);
			g.addEdge(t, s, dest);
		}
		g.removeVertex(s1);
		g.removeVertex(s2);
		return s;
	}
	
	/** copies src outbounds into dest ones.
	 * 
	 * @param src
	 * @param dest
	 */
	void mergeOutbounds(S src, S dest) {
		// copy oldout  outbonds into source
		for (T t : g.getOutEdges(src)) {
			S sdest = g.getDest(t);
			g.addEdge(cloneTransition(t), dest, sdest);
		}
	}

	/** clone this grex
	 * 
	 * @return
	 */
	<G extends Grex<S, T>> G dup() {

		G that = newInstance();
		// graph
		Map<S, S> map = copyGraphInto(that);
		//bounds
		that.in = map.get(this.in);
		for (S out : this.outs)
			that.outs.add(map.get(out));
		that.assertGraph();
		return that;
	}

	/** return a newly created state object
	 * 
	 * @return
	 */
	protected abstract S newState();
	
	/** duplicates the transition object.
	 * 
	 * @param t
	 * @return
	 */
	protected abstract T cloneTransition(T t);
	/** creates a new instance of this grex
	 * 
	 * @return
	 */
	protected abstract <G extends Grex<S, T>> G newInstance();
}
